package solution.dp;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

import org.apache.commons.lang.StringUtils;
import org.junit.Test;

import com.google.inject.internal.Lists;

import data.Data;

/**
 * @author <a href="www.sureinterview.com">SureInterview</a>
 * 
 */
public class LowerWord {

	// a cache that is used by this top-down DP.
	Map<String, String> cache = new HashMap<String, String>();

	String getLowerWordInDict(List<String> words) {
		return getLowerWordRec(words, words.size());
	}

	String getLowerWordRec(List<String> words, int length) {
		String key = StringUtils.join(words, ",") + ":" + length;
		if (cache.containsKey(key))
			return cache.get(key);

		if (length == 1) {
			String smallest = smallestWord(words);
			cache.put(key, smallest);
			return smallest;
		}

		List<String> results = Lists.newArrayList();
		for (String w : words) {
			List<String> restWords = Lists.newArrayList(words);
			restWords.remove(w);
			String tmpResult = w + getLowerWordRec(restWords, length - 1);
			// System.out.println(tmpResult);
			results.add(tmpResult);
		}

		String smallest = smallestWord(results);
		cache.put(key, smallest);
		return smallest;
	}

	String smallestWord(List<String> words) {
		if (words == null)
			return null;
		String small = words.get(0);
		for (String wd : words) {
			if (wd.compareTo(small) < 0) {
				small = wd;
			}
		}
		return small;
	}

	@Test
	public void test() {
		// List<String> words = Lists.newArrayList(new String[] { "a", "aa",
		// "aaa", "c", "cc", "ccc", "b", "bb", "bbb" });
		//
		// System.out.println(getLowerWordInDict(words));

		// cupfacebookforhackerstudentsstudious
		// duzklvrawqrc
		// dyroiymybeaxeyubxzdr
		// bwjibwjibwjijp
		// dcyihopjijliuiuy

		String data = Data.getData("facebook.txt");
		String[] lines = data.split("\n");
		int lineCnt = Integer.valueOf(lines[0]);
		for (int i = 1; i <= lineCnt; i++) {
			String[] words = lines[i].split(" +");
			List<String> wdList = Lists.newArrayList(words);
			wdList.remove(0);
			System.out.println(getLowerWordInDict(wdList));
		}
	}
}
